/*
 * @lc app=leetcode.cn id=688 lang=typescript
 *
 * [688] “马”在棋盘上的概率
 */

// @lc code=start
function knightProbability(n: number, k: number, row: number, column: number): number {
  const dirs = [
    [-2, -1],
    [-2, 1],
    [2, -1],
    [2, 1],
    [-1, -2],
    [-1, 2],
    [1, -2],
    [1, 2],
  ];
  const dp = new Array(k + 1)
    .fill(0)
    .map((_) => new Array(n).fill(0).map((_) => new Array(n).fill(0)));

  for (let step = 0; step <= k; step++) {
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        if (step === 0) {
          dp[step][i][j] = 1;
        } else {
          for (const [x, y] of dirs) {
            const ni = i + x;
            const nj = j + y;
            if (ni < 0 || ni >= n) continue;
            if (nj < 0 || nj >= n) continue;
            dp[step][i][j] += dp[step - 1][ni][nj] / 8;
          }
        }
      }
    }
  }

  return dp[k][row][column];
}
// @lc code=end
